package com.ztom.top100;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 合并区间
 * <p>
 * https://leetcode-cn.com/problems/merge-intervals/
 *
 * @author ZhangTao
 */
public class Code26Merge {

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{};
        }
        int[][] res = new int[intervals.length][2];
        // 根据区间左端点排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // 记录合并后的区间的位置
        int index = -1;
        for (int[] interval : intervals) {
            if (index == -1 || res[index][1] < interval[0]) {
                // 在第一个区间, 或区间无法合并, 直接记录新的区间
                res[++index] = interval;
            } else {
                // 合并两个区间
                res[index][1] = Math.max(res[index][1], interval[1]);
            }
        }

        // 过滤掉合并产生的空区间
        return Arrays.copyOf(res, index + 1);
    }
}
